package 分治.归并排序;

public class 排序数组912 {

    int [] tmp ; //写成全局对象，不用每次调用方法都要new，优化时间
    public int[] sortArray(int [] nums)
    {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    public void mergeSort(int [] nums,int left,int right)
    {
        if(left >= right) return ;
        //1.根据中间划分区间
        int mid = (left+right)/2;

        //2.先把左右区间进行排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        //3.合并有序数组
        int cur1 = left,cur2 = mid+1,i=0;
        while(cur1<=mid && cur2<=right)
            tmp[i++] = nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];

        //4.处理还没有遍历完的数组
        while(cur1<=mid) tmp[i++] = nums[cur1++];
        while(cur2<=right) tmp[i++] = nums[cur2++];
        // 5.还原
        for(int z = left ;z<=right;z++)
            nums[z] = tmp[z-left];//因为tmp从left开始计数，减去刚好

    }
}
